#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>

using namespace std;

class Sort
{
public:
	void Print(vector<int>& nums)
	{
		for (auto& e : nums)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void InsertSort(vector<int>& nums)
	{
		int size = nums.size();
		for (int i = 0; i < size - 1; i++)
		{
			for (int j = i; j >= 0 && nums[j] > nums[j + 1]; j--)
			{
				swap(nums[j], nums[j + 1]);
			}
		}
	}

	void ShellSort(vector<int>& nums, int n)
	{
		int size = nums.size();
		int gap = n;
		while (gap > 1)
		{
			gap = gap / 3 + 1;
			for (int i = 0; i < size - gap; i++)
			{
				for (int j = i; j >= 0 && nums[j] > nums[j + gap]; j -= gap)
				{
					swap(nums[j], nums[j + gap]);
				}
			}
		}
	}

	void SelectSort(vector<int>& nums)
	{
		int size = nums.size();
		int left = 0, right = size - 1;
		while (left < right)
		{
			int mini = left, maxi = left;
			for (int i = left + 1; i <= right; i++)
			{
				if (nums[i] < nums[mini])
					mini = i;
				if (nums[i] > nums[maxi])
					maxi = i;
			}
			swap(nums[left], nums[mini]);

			if (left == maxi)
				maxi = mini;

			swap(nums[right], nums[maxi]);

			left++;
			right--;
		}
	}

	void Ajustup(vector<int>& nums, int child)
	{
		int parent = (child - 1) / 2;
		while (parent >= 0)
		{
			if (nums[parent] < nums[child])
			{
				swap(nums[parent], nums[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
	}

	void Ajustdown(vector<int>& nums, int size, int parent)
	{
		int child = parent * 2 + 1;
		while (child < size)
		{
			if (child + 1 < size && nums[child] < nums[child + 1])
				child += 1;
			if (nums[parent] < nums[child])
			{
				swap(nums[parent], nums[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
				break;
		}
	}
	void HeapSort(vector<int>& nums)
	{
		int size = nums.size();
		//priority_queue<int, vector<int>, less<int>> pq(nums.begin(), nums.end()); // 排升序建大堆
		//nums.clear();
		//while (!pq.empty())
		//{
		//	nums.push_back(pq.top());
		//	pq.pop();
		//}
		for (int i = (size - 1 - 1) / 2; i >= 0; i--) // 排升序建大堆
		{
			Ajustdown(nums, size, i);
		}
		int end = size - 1;
		while (end > 0)
		{
			swap(nums[0], nums[end]);
			Ajustdown(nums, end, 0);
			end--;
		}
	}

	void BubbleSort(vector<int>& nums)
	{
		int size = nums.size();
		bool flag = false;
		for (int i = 0; i < size - 1; i++)
		{
			for (int j = 0; j < size - 1 - i; j++)
			{
				if (nums[j] > nums[j + 1])
				{
					swap(nums[j], nums[j + 1]);
					flag = true;
				}
			}
			if (!flag) break;
		}
	}

	// Hoare
	//void QuickSort(vector<int>& nums, int begin, int end)
	//{
	//	if (begin >= end) return;
	//	int left = begin, right = end;
	//	int keyi = left;
	//	while (left < right)
	//	{
	//		while (left < right && nums[right] >= nums[keyi]) right--;
	//		while (left < right && nums[left] <= nums[keyi]) left++;

	//		swap(nums[left], nums[right]);
	//	}
	//	swap(nums[left], nums[keyi]);
	//	keyi = left;
	//	QuickSort(nums, begin, keyi - 1);
	//	QuickSort(nums, keyi + 1, end);
	//}

	// 三数取中
	int GetMidIndex(vector<int>& nums, int begin, int end)
	{
		int mid = begin + (end - begin) / 2;
		if (nums[begin] < nums[mid])
		{
			if (nums[end] < nums[begin])
				return begin;
			else if (nums[mid] < nums[end])
				return mid;
			else
				return end;
		}
		else // nums[mid] <= nums[begin]
		{
			if (nums[end] < nums[mid])
				return mid;
			else if (nums[begin] < nums[end])
				return begin;
			else
				return end;
		}
	}

	// 双指针
	void QuickSort(vector<int>& nums, int begin, int end)
	{
		if (begin >= end) return;

		int mid = GetMidIndex(nums, begin, end);
		swap(nums[mid], nums[begin]);

		int keyi = begin;
		int prev = begin;
		int cur = prev + 1;

		while (cur <= end)
		{
			if (nums[cur] < nums[keyi] && ++prev != cur)
			{
				swap(nums[cur], nums[prev]);
			}
			cur++;
		}
		swap(nums[keyi], nums[prev]);
		keyi = prev;

		QuickSort(nums, begin, keyi - 1);
		QuickSort(nums, keyi + 1, end);
	}

	void _MergeSort(vector<int>& nums, int begin, int end, vector<int>& tmp)
	{
		if (begin >= end) return;

		int mid = begin + (end - begin) / 2;

		_MergeSort(nums, begin, mid, tmp);
		_MergeSort(nums, mid + 1, end, tmp);

		int begin1 = begin, end1 = mid;
		int begin2 = mid + 1, end2 = end;
		int n = begin;
		while (begin1 <= end1 && begin2 <= end2)
		{
			if (nums[begin1] <= nums[begin2])
				tmp[n++] = nums[begin1++];
			else
				tmp[n++] = nums[begin2++];
		}

		while (begin1 <= end1)
			tmp[n++] = nums[begin1++];
		while (begin2 <= end2)
			tmp[n++] = nums[begin2++];

		for (int i = begin; i <= end; i++)
		{
			nums[i] = tmp[i];
		}
	}

	void MergeSort(vector<int>& nums)
	{
		vector<int> tmp(nums.size());
		_MergeSort(nums, 0, nums.size() - 1, tmp);
	}
};

int main()
{
	vector<int> v = { 9,1,3,7,4,6,2,5,8 };
	Sort sort;
	//sort.BubbleSort(v);
	//sort.InsertSort(v);
	//sort.SelectSort(v);
	//sort.ShellSort(v, 6);
	//sort.HeapSort(v);
	//sort.QuickSort(v, 0, v.size() - 1);
	sort.MergeSort(v);
	sort.Print(v);
	return 0;
}